\chapter {PageRank}
%TODO Intro PageRank
{\bf PageRank} è un algoritmo di analisi che assegna un peso numerico ad ogni
elemento di un collegamento ipertestuale d'un insieme di documenti, come ad
esempio il World Wide Web, con lo scopo di quantificare la sua importanza
relativa all'interno della serie. L'algoritmo può essere applicato a tutti gli
insiemi di oggetti collegati da citazioni e riferimenti reciproci. Il peso
numerico assegnato ad un dato elemento E è chiamato anche "il PageRank di E",
siglato in PR (E).
\subsection {Variabili Casuali}
Una {\bf Variabile Casuale} consiste nel risultato non predicibile di un
esperimento, ripetendo più volte lo stesso infatti il risultato può variare,
come succede per esempio con l lancio di una moneta o di un dado, quindi è
possibile solo uno studio probabilistico dell'esperimento.\\
Le variabili casuali si suddividono in variabili di tipo discreto o continuo.
Una {\bf variabile casuale di tipo discreto} è un risultato finito o numerabile,
al contrario quelle di tipo {\bf continuo} rappresentano risultati di
esperimenti di cui il risultato è nel continuo, per esempio il rilevamento della
temperatura all'interno di una stanza.\\
\subsection{Distribuzione di probabilità}
Una {\bf distribuzione di probabilità} associa ad ogni valore possibile la sua
probabilità. La somma di tutte le singole probabilità deve essere uguale a 1,
quindi ognuna di esse è maggiore di 0 e compresa tra 0 e 1.\\
\insertImage{0.8}{pdf_graph.JPG}{Rappresentazione di un istogrammacorrispondente alla distribuzione di probabilità }
\subsection {Funzione di Distribuzione Cumulativa}
Una {\bf distribuzione cumulativa CDF} viene utilizzata nel caso in cui sullo
spazio di probabilità sia applicabile un ordinamento completo, per esempio nel
caso in cui si lavora sui dei numeri.\\
%TODO INSERISCI ESEMPIO DI ISTOGRAMMA = FUNZIONE DI Distribuzione completa Funzione a scalini'
E' possibile passare da una distribuzione di probabilità ad una di tipo
cumulativa, ogni probabilità viene calcolata sommando le probabilità precedenti
con quella dell'elemento considerato, come nell'esempio	
\begin{center}
\begin{tabular}{ | l | l | }
\hline
P(1) = 0.1 	& C(1)= 0.1\\ \hline
P(2) = 0.3 	& C(2)= 0.4\\ \hline
P(3) = 0.4 	& C(3)= 0.8\\ \hline
P(4) = 0.2 	& C(4)= 1\\ \hline
\end{tabular}
\end{center}


\subsection {Processi Stocastici}
Un {\bf Processo Stocastico} permette di studiare la relazione che occorre tra
diverse variabili casuali, per esempio nel lancio di una moneta è del tutto
inutile studiare e osservare i risultati precedenti perchè tutti gli eventi sono
slegati uno dall'altro e lo studio di questi non permette nessuna predizione.\\
\subsection {Processi di Markov}
Un processo stocastico markoviano o processo di Markov è un processo stocastico
nel quale la probabilità di transizione che determina il passaggio ad uno stato
di sistema dipende unicamente dallo stato di sistema immediatamente precedente,
proprietà {\bf Memory Less} e non dal come si è giunti a tale stato.\\
Viene introdotto il concetto di Stato discreto, ad un dato tempo T, Il punto di
partenza è lo {Stato Iniziale} e a partire da questo si vuole studiare la
dinamica utilizzando una funzione di distribuzione di probabilità e il tempo
impiegato a raggiungere un determinato stato, {\bf Transient}.\\
Il tempo si suddivide in discreto e continuo, nel primo si parte da un
campionamento, ovvero dal risultato di diversi esperimenti ordinabili mentre nel
secondo caso i risultati non sono ordinabili ma rilevati in maniera
arbitraria.\\\\
Si definisce {Tempo di Soggiorno} il tempo in cui il sistema rimane nello stesso
stato e in un Processo di Markov a tempo discreto il tempo di soggiorno è una
distribuzione di due tipi:
\begin{itemize}				
\item {\bf Geometrico} se il tempo è discreto e vale $P\{st(t)=s\}= P(1-p)^s$
\item {\bf Esponenziale} se il tempo è continuo e vale$P\{st(t)=s\}= e^{-\lambda
s}$

\end{itemize}
p e $\lambda $ sono dei parametri che caratterizzano la distribuzione di
probabilità.

%X( t_i)= x indica il risultato della variabile casuale al tempo t
\subsection{Condizioni di Ergodicità}
$pigreco   P^n = pigreco_{n}$
per n che tende all'infinito $pigreco_{n}$ =?
Se il limite esiste $pigreco_{n}$ = distribuzione stazionaria pigreco calcolata
sull'autovettore lamda=1, quindi arrivati a questo punto lo stato iniziale non
risulta essere più rilevante, infatti lo stato ennesimo è indipendente dallo
quello iniziale, ma dipende solo dalla matrice di transizione di stato.\\
Nel caso di un sistema non Ergodico non esiste il limite perchè l'andamento
del'autovettore ha un comportamento periodico.\\
%Es fatto a lezione [1, 0 , 0 ,0]\\
%	[0, 0.9, 0.1, 0]
%	[0.5, 0, 0, 0.5] =pigrego 4
%	[0,0.5, 0.5,0] = pigrego 5

\section{Misure di centralità}
La valutazione di una pagina in PageRank non avviene solamente guardando il
contenuto della pagina, ma anche attraverso un sistema di referenziamento,
ovvero ogni pagina che effettua il link ad un'altra pagina aumenta l'importanza
associata a quel sito, risulta importante però anche l'autorevolezza del
referenziatore.\\
\subsection {Eigenvector Centrality}
Una prima misura di centralità è data dalla {\bf Eigenvector Centrality}, ovvero
per valutare l'importanza di un nodo si prendono in considerazione il numero
degli archi entranti, come per stimare la {\bf Degree Centrality}, che però non
è sufficiente, infatti bisogna anche considerare l'autorevolezza del nodo che
referenzia.\\
Il calcolo dell' Eigenvector Centrality avviene tramite l'uso degli autovettori
e un valore molto alto implica che:
\begin{itemize}
\item Un nodo ha molti vicini, anche di poca importanza.
\item Oppure pochi vicini ma di elevata importanza.
\end{itemize}
% %TODO Inserire immagine ed esempio negativo
\subsection{ Katz Centrality}
Una ulteriore approsimazione dell'EigenVector Centrality è la {\bf Katz
Centrality}, nodi che hanno un numero elevato di link uscenti ma nessuno
entrante con la prima avevano un valore molto basso, mentre con quest'ultima
viene comunque data un valore di base all'autovettore.\\
Il modello proposto da Katz però non è adatto per i motori di ricerca, infatti
un nodo con un'alta centralità trasferisce questa anche al nodo che referenzia.
\subsection {PageRank centrality}
L'algoritmo di Brin e Page distribuisce comunque la centralità del nodo di
partenza, ma in proporzione al numero di link uscenti da questo.

\section{Catene di Markov}
Il cammino sul web si può rappresentare come una catena di Markov con i seguenti
fattori:
\begin{itemize}
\item Stato: pagina visualizzata.
\item Matrice di transizione: la probabilità che durante la Random Walk si segua
un dato arco.
\item Dalla stessa pagina, assegnamo la stessa probabilità $1/out_{j}$ ad ogni
arco uscente.
\end{itemize}.
La matrice di transizione si ottiene rendendo stocastica per righe la matrice di
adiacenza.\\
L'obiettivo è trovare una distribuzione stazionaria, che dipenda dalla
distribuzione iniziale e che faccia emergere le pagine veramente importanti, ma
questo è possibile solamente dopo aver applicato alcune modifiche alla matrice
calcolata in precedenza.\\
\subsection{Vicoli ciechi}
I vicoli ciechi sono dei nodi all'interno del grafo che fermano la distribuzione
del ranking, ovvero ricevono del ranking ma non ne ridistribuiscono non avendo
dei link uscenti. Per risolvere il problema dei vicoli ciechi si aggiungono dei
link artificialmente, nella matrice di adiacenza il nodo avrebbe tutti 0 ma per
questo vengono inseriti link verso tutti i nodi del grafo, ognuno con la stessa
probabilità\\
%TODO INSERIRE IMMAGINE
Una soluzione più unfair consiste nell'aggiungere un link alla pagina stessa.
\subsection {Nodi Sink}
I {\bf Nodi Sink} sono quei nodi che ricevono dei link entranti e gli unici link
uscenti che possiedono sono all'interno della "comunità" generando così una
struttura di accumulazione.\\
Si risolve ridistribuendo parte del ranking perso in maniera uniforme tra tutti
i link del grafo.
\section{La matrice di Google}
Dato che $lamda_1 $vale 1 $lamda_2$ rappresenta quindi il valore di convergenza,
il valore ottimale di $lamda_2$ calcolato da Google vale 0.85.%CONTROLLA se è giusto.
